package solution1.yonyou_solution;

<<<<<<< HEAD:yonyou_solution/Solution1.java
//import javafx.util.Pair;
//
//import java.util.*;
//   class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode() {}
//      TreeNode(int val) { this.val = val; }
//      TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;
//      }
//  }
//class ListNode {
//     int val;
//     ListNode next;
//     ListNode() {}
//     ListNode(int val) { this.val = val; }
//     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// }
//
//public class Solution1 {
//
////     //1.反转链表
////    public ListNode reverseList(ListNode head) {
////        if(head == null || head.next == null) {
////            return head;
////        }
////        ListNode cur = head.next;
////        head.next = null;
////        while(cur != null) {
////            ListNode curNext = cur.next;
////            cur.next = head;
////            head = cur;
////            cur = curNext;
////        }
////        return head;
////    }
//
//    //2。链表两两交换节点
//    public ListNode swapPairs(ListNode head) {
=======

import java.util.*;
   class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution1 {

//     //1.反转链表
//    public ListNode reverseList(ListNode head) {
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/yonyou_solution/Solution1.java
//        if(head == null || head.next == null) {
//            return head;
//        }
//        ListNode dummy = new ListNode();
//        ListNode prev = dummy;
//        while(head != null && head.next != null) {
//            ListNode cur = head.next;
//            head.next = cur.next;
//            cur.next = head;
//            prev.next = cur;
//            prev = head;
//            head = head.next;
//        }
//        return dummy.next;
//    }
//
//    //3.删除链表的倒数第 N 个结点
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode fast = head;
//        while(n > 0) {
//            fast = fast.next;
//            n--;
//        }
//        ListNode dummy = new ListNode();
//        dummy.next = head;
//        ListNode slow = head;
//        ListNode prev = dummy;
//        while(fast != null) {
//            fast = fast.next;
//            prev = slow;
//            slow = slow.next;
//        }
//        prev.next = slow.next;
//        return dummy.next;
//    }
//
//    //4.面试题 02.07. 链表相交
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode curA = headA;
//        ListNode curB = headB;
//        int lenA = 0;
//        int lenB = 0;
//        while(curA != null) {
//            curA = curA.next;
//            lenA++;
//        }
//        while(curB != null) {
//            curB = curB.next;
//            lenB++;
//        }
//        curA = headA;
//        curB = headB;
//        if(lenA > lenB) {
//            int ans = lenA - lenB;
//            while(ans > 0) {
//                curA = curA.next;
//                ans--;
//            }
//            while(curA != null && curA != curB) {
//                curA = curA.next;
//                curB = curB.next;
//            }
//        } else {
//            int ans = lenB - lenA;
//            while(ans > 0) {
//                curB = curB.next;
//                ans--;
//            }
//            while(curA != null && curA != curB) {
//                curA = curA.next;
//                curB = curB.next;
//            }
//        }
//        return curA == null ? null : curA;
//    }
//
//    //5.环形链表 II
//    public ListNode detectCycle(ListNode head) {
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow) {
//                break;
//            }
//        }
//        if(fast == null || fast.next == null) {
//            return null;
//        }
//        slow = head;
//        while(slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return slow;
//    }
//
//    //6.链表重排
//    private ListNode reverseList(ListNode head) {
//        if(head == null || head.next == null) {
//            return head;
//        }
//        ListNode cur = head;
//        ListNode curNext = head.next;
//        cur.next = null;
//        while(curNext != null) {
//            ListNode ccNext = curNext.next;
//            curNext.next = cur;
//            cur = curNext;
//            curNext = ccNext;
//        }
//        return cur;
//    }
//
//    public void reorderList(ListNode head) {
//        if(head == null || head.next == null) {
//            return ;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode mid = null;
//        while(fast != null && fast.next != null) {
//            mid = slow;
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        mid.next = null;
//        ListNode cur2 = reverseList(slow);
//        ListNode cur = head;
//        ListNode prev = null;
//        while(cur != null) {
//            prev = cur2;
//            ListNode curNext = cur.next;
//            cur.next = cur2;
//            ListNode cur2Next = cur2.next;
//            cur2.next = curNext;
//            cur2 = cur2Next;
//            cur = curNext;
//        }
//        if(cur2 != null) {
//            prev.next = cur2;
//        }
//    }
<<<<<<< HEAD:yonyou_solution/Solution1.java
=======

    //2。链表两两交换节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        ListNode prev = dummy;
        while(head != null && head.next != null) {
            ListNode cur = head.next;
            head.next = cur.next;
            cur.next = head;
            prev.next = cur;
            prev = head;
            head = head.next;
        }
        return dummy.next;
    }

    //3.删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while(n > 0) {
            fast = fast.next;
            n--;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode slow = head;
        ListNode prev = dummy;
        while(fast != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        prev.next = slow.next;
        return dummy.next;
    }

    //4.面试题 02.07. 链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != null) {
            curA = curA.next;
            lenA++;
        }
        while(curB != null) {
            curB = curB.next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        if(lenA > lenB) {
            int ans = lenA - lenB;
            while(ans > 0) {
                curA = curA.next;
                ans--;
            }
            while(curA != null && curA != curB) {
                curA = curA.next;
                curB = curB.next;
            }
        } else {
            int ans = lenB - lenA;
            while(ans > 0) {
                curB = curB.next;
                ans--;
            }
            while(curA != null && curA != curB) {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return curA == null ? null : curA;
    }

    //5.环形链表 II
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //6.链表重排
    private ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curNext = head.next;
        cur.next = null;
        while(curNext != null) {
            ListNode ccNext = curNext.next;
            curNext.next = cur;
            cur = curNext;
            curNext = ccNext;
        }
        return cur;
    }

    public void reorderList(ListNode head) {
        if(head == null || head.next == null) {
            return ;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode mid = null;
        while(fast != null && fast.next != null) {
            mid = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        mid.next = null;
        ListNode cur2 = reverseList(slow);
        ListNode cur = head;
        ListNode prev = null;
        while(cur != null) {
            prev = cur2;
            ListNode curNext = cur.next;
            cur.next = cur2;
            ListNode cur2Next = cur2.next;
            cur2.next = curNext;
            cur2 = cur2Next;
            cur = curNext;
        }
        if(cur2 != null) {
            prev.next = cur2;
        }
    }

    //7.用队列实现栈
    class MyStack {

        private Queue<Integer> queue1 = new LinkedList<>();
        private Queue<Integer> queue2 = new LinkedList<>();

        public MyStack() {

        }

        public void push(int x) {
            while(!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            queue1.offer(x);
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }
        }

        public int pop() {
            return queue1.poll();
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }

    //8.用栈实现队列
    class MyQueue {

        private Stack<Integer> stack1 = new Stack<>();
        private Stack<Integer> stack2 = new Stack<>();

        public MyQueue() {

        }

        public void push(int x) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            stack1.push(x);
            while(!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
        }

        public int pop() {
            return stack1.pop();
        }

        public int peek() {
            return stack1.peek();
        }

        public boolean empty() {
            return stack1.isEmpty();
        }
    }

    //9.括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if(ch == ')' || ch == ']' || ch == '}') {
                if(!stack.isEmpty()) {
                    char ans = stack.peek();
                    if((ans == '(' && ch == ')') ||
                            (ans == '[' && ch == ']') ||
                            (ans == '{' && ch == '}')) {
                        stack.pop();
                        continue;
                    }
                }
            }
            stack.push(ch);
        }
        return stack.isEmpty();
    }

    //10.删除字符串中的所有相邻重复项
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if(!stack.isEmpty() && stack.peek() == ch) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        int size = stack.size();
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < size; i++) {
            stringBuilder.append(stack.pop());
        }
        return new String(stringBuilder.reverse());
    }

    //11.逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        int len = tokens.length;
        for(int i = 0; i < len; i++) {
            String str = tokens[i];
            int slen = str.length();
            if(slen != 1) {
                stack.push(Integer.parseInt(str));
            } else {
                char ch = str.charAt(0);
                if(ch >= '0' && ch <= '9') {
                    stack.push(Integer.parseInt(str));
                } else {
                    int n2 = stack.pop();
                    int n1 = stack.pop();
                    switch(ch) {
                        case '+':
                            stack.push(n1 + n2);
                            break;
                        case '-':
                            stack.push(n1 - n2);
                            break;
                        case '*':
                            stack.push(n1 * n2);
                            break;
                        case '/':
                            stack.push(n1 / n2);
                            break;
                    }
                }
            }
        }
        return stack.pop();
    }

    //12、滑动窗口最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len - k + 1];
        int index = 0;
        Deque<Integer> queue = new LinkedList<>();
        for(int i = 0; i < len; i++) {
            if(i < k - 1) {
                while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                    queue.pollLast();
                }
                queue.offerLast(nums[i]);
            } else {
                while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                    queue.pollLast();
                }
                queue.offerLast(nums[i]);
                res[index++] = queue.peekFirst();
                if(!queue.isEmpty() && queue.peekFirst() == nums[i - k + 1]) {
                    queue.pollFirst();
                }
            }
        }
        return res;
    }

//    //13.前 K 个高频元素
//    public int[] topKFrequent(int[] nums, int k) {
//        //用 map 统计出现次数
//        Map<Integer, Integer> map = new HashMap<>();
//        int len = nums.length;
//        for(int i = 0; i < len; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//        }
//        //建立小根堆
//        PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {
//            @Override
//            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
//                return o1.getValue() - o2.getValue();
//            }
//        });
//        //插入到小根堆
//        int index = 0;
//        for(int key : map.keySet()) {
//            if(index < k) {
//                queue.offer(new Pair<>(key, map.get(key)));
//            } else {
//                if(queue.peek().getValue() < map.get(key)) {
//                    queue.poll();
//                    queue.offer(new Pair<>(key, map.get(key)));
//                }
//            }
//            index++;
//        }
//        int[] res = new int[k];
//        for(int i = 0; i < k; i++) {
//            res[i] = queue.poll().getKey();
//        }
//        return res;
//    }
//

    //14.二叉树BFS
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            res.add(new ArrayList<>(list));
        }
        return res;
    }

    //15.翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //16.对称二叉树
    private boolean isFlag(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        }
        if((left == null && right != null) ||
                (left != null && right == null)) {
            return false;
        }
        if(left.val != right.val) {
            return false;
        }
        return isFlag(left.left, right.right) &&
                isFlag(left.right, right.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isFlag(root.left, root.right);
    }
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/yonyou_solution/Solution1.java
//
//    //7.用队列实现栈
//    class MyStack {
//
//        private Queue<Integer> queue1 = new LinkedList<>();
//        private Queue<Integer> queue2 = new LinkedList<>();
//
//        public MyStack() {
//
//        }
//
//        public void push(int x) {
//            while(!queue1.isEmpty()) {
//                queue2.offer(queue1.poll());
//            }
//            queue1.offer(x);
//            while(!queue2.isEmpty()) {
//                queue1.offer(queue2.poll());
//            }
//        }
//
//        public int pop() {
//            return queue1.poll();
//        }
//
//        public int top() {
//            return queue1.peek();
//        }
//
//        public boolean empty() {
//            return queue1.isEmpty();
//        }
//    }
//
//    //8.用栈实现队列
//    class MyQueue {
//
//        private Stack<Integer> stack1 = new Stack<>();
//        private Stack<Integer> stack2 = new Stack<>();
//
//        public MyQueue() {
//
//        }
//
//        public void push(int x) {
//            while(!stack1.isEmpty()) {
//                stack2.push(stack1.pop());
//            }
//            stack1.push(x);
//            while(!stack2.isEmpty()) {
//                stack1.push(stack2.pop());
//            }
//        }
//
//        public int pop() {
//            return stack1.pop();
//        }
//
//        public int peek() {
//            return stack1.peek();
//        }
//
//        public boolean empty() {
//            return stack1.isEmpty();
//        }
//    }
//
//    //9.括号匹配
//    public boolean isValid(String s) {
//        Stack<Character> stack = new Stack();
//        int len = s.length();
//        for(int i = 0; i < len; i++) {
//            char ch = s.charAt(i);
//            if(ch == ')' || ch == ']' || ch == '}') {
//                if(!stack.isEmpty()) {
//                    char ans = stack.peek();
//                    if((ans == '(' && ch == ')') ||
//                            (ans == '[' && ch == ']') ||
//                            (ans == '{' && ch == '}')) {
//                        stack.pop();
//                        continue;
//                    }
//                }
//            }
//            stack.push(ch);
//        }
//        return stack.isEmpty();
//    }
//
//    //10.删除字符串中的所有相邻重复项
//    public String removeDuplicates(String s) {
//        Stack<Character> stack = new Stack();
//        int len = s.length();
//        for(int i = 0; i < len; i++) {
//            char ch = s.charAt(i);
//            if(!stack.isEmpty() && stack.peek() == ch) {
//                stack.pop();
//            } else {
//                stack.push(ch);
//            }
//        }
//        int size = stack.size();
//        StringBuilder stringBuilder = new StringBuilder();
//        for(int i = 0; i < size; i++) {
//            stringBuilder.append(stack.pop());
//        }
//        return new String(stringBuilder.reverse());
//    }
//
//    //11.逆波兰表达式求值
//    public int evalRPN(String[] tokens) {
//        Stack<Integer> stack = new Stack();
//        int len = tokens.length;
//        for(int i = 0; i < len; i++) {
//            String str = tokens[i];
//            int slen = str.length();
//            if(slen != 1) {
//                stack.push(Integer.parseInt(str));
//            } else {
//                char ch = str.charAt(0);
//                if(ch >= '0' && ch <= '9') {
//                    stack.push(Integer.parseInt(str));
//                } else {
//                    int n2 = stack.pop();
//                    int n1 = stack.pop();
//                    switch(ch) {
//                        case '+':
//                            stack.push(n1 + n2);
//                            break;
//                        case '-':
//                            stack.push(n1 - n2);
//                            break;
//                        case '*':
//                            stack.push(n1 * n2);
//                            break;
//                        case '/':
//                            stack.push(n1 / n2);
//                            break;
//                    }
//                }
//            }
//        }
//        return stack.pop();
//    }
//
//    //12、滑动窗口最大值
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        int len = nums.length;
//        int[] res = new int[len - k + 1];
//        int index = 0;
//        Deque<Integer> queue = new LinkedList<>();
//        for(int i = 0; i < len; i++) {
//            if(i < k - 1) {
//                while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
//                    queue.pollLast();
//                }
//                queue.offerLast(nums[i]);
//            } else {
//                while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
//                    queue.pollLast();
//                }
//                queue.offerLast(nums[i]);
//                res[index++] = queue.peekFirst();
//                if(!queue.isEmpty() && queue.peekFirst() == nums[i - k + 1]) {
//                    queue.pollFirst();
//                }
//            }
//        }
//        return res;
//    }
//
//    //13.前 K 个高频元素
//    public int[] topKFrequent(int[] nums, int k) {
//        //用 map 统计出现次数
//        Map<Integer, Integer> map = new HashMap<>();
//        int len = nums.length;
//        for(int i = 0; i < len; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//        }
//        //建立小根堆
//        PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {
//            @Override
//            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
//                return o1.getValue() - o2.getValue();
//            }
//        });
//        //插入到小根堆
//        int index = 0;
//        for(int key : map.keySet()) {
//            if(index < k) {
//                queue.offer(new Pair<>(key, map.get(key)));
//            } else {
//                if(queue.peek().getValue() < map.get(key)) {
//                    queue.poll();
//                    queue.offer(new Pair<>(key, map.get(key)));
//                }
//            }
//            index++;
//        }
//        int[] res = new int[k];
//        for(int i = 0; i < k; i++) {
//            res[i] = queue.poll().getKey();
//        }
//        return res;
//    }
//
//
//    //14.二叉树BFS
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> res = new ArrayList<>();
//        if(root == null) {
//            return res;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()) {
//            List<Integer> list = new ArrayList<>();
//            int size = queue.size();
//            while(size > 0) {
//                TreeNode node = queue.poll();
//                list.add(node.val);
//                if(node.left != null) {
//                    queue.offer(node.left);
//                }
//                if(node.right != null) {
//                    queue.offer(node.right);
//                }
//                size--;
//            }
//            res.add(new ArrayList<>(list));
//        }
//        return res;
//    }
//
//    //15.翻转二叉树
//    public TreeNode invertTree(TreeNode root) {
//        if(root == null) {
//            return null;
//        }
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
//    }
//
//    //16.对称二叉树
//    private boolean isFlag(TreeNode left, TreeNode right) {
//        if(left == null && right == null) {
//            return true;
//        }
//        if((left == null && right != null) ||
//                (left != null && right == null)) {
//            return false;
//        }
//        if(left.val != right.val) {
//            return false;
//        }
//        return isFlag(left.left, right.right) &&
//                isFlag(left.right, right.left);
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isFlag(root.left, root.right);
//    }
////
////    //17.二叉树的最大深度
////    public int maxDepth(TreeNode root) {
////        if(root == null) {
////            return 0;
////        }
////        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
////    }
//
//    //18.二叉树的最小深度
//    public int minDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        if(root.left == null && root.right == null) {
//            return 1;
//        }
//        if(root.left != null && root.right == null) {
//            return minDepth(root.left) + 1;
//        }
//        if(root.left == null && root.right != null) {
//            return minDepth(root.right) + 1;
//        }
//        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
//    }
//
//    //19.完全二叉树的节点个数
//    public int countNodes(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        if(root.left == null) {
//            return 1;
//        }
//        return countNodes(root.left) + countNodes(root.right) + 1;
//    }
//
//    //20.平衡二叉树
//    private int maxDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
//    }
//
//    public boolean isBalanced(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
//    }
//
//    //21.二叉树的所有路径
//    public List<String> binaryTreePaths(TreeNode root) {
//        List<String> res = new ArrayList<>();
//        if(root == null) {
//            return res;
//        }
//        StringBuilder path = new StringBuilder();
//        path.append(root.val);
//        dfs(root.left, res, path);
//        dfs(root.right, res, path);
//        if(root.left == null && root.right == null) {
//            res.add(path.toString());
//        }
//        return res;
//    }
//
//    private void dfs(TreeNode root, List<String> res, StringBuilder path) {
//        if(root == null) {
//            return;
//        }
//        path.append("->");
//        String val = String.valueOf(root.val);
//        path.append(val);
//        if(root.left == null && root.right == null) {
//            res.add(new String(path));
//        }
//        dfs(root.left, res, path);
//        dfs(root.right, res, path);
//        int len = val.length();
//        path.delete(path.length() - len - 2, path.length());
//    }
//
//
////    //22.左叶子之和
////    private int sum = 0;
////    public int sumOfLeftLeaves(TreeNode root) {
////        if(root == null) {
////            return 0;
////        }
////        dfs(root, null);
////        return sum;
////    }
////
////    private void dfs(TreeNode root, TreeNode prev) {
////        if(root == null) {
////            return;
////        }
////        dfs(root.left, root);
////        dfs(root.right, root);
////        if(prev == null) {
////            return;
////        }
////        if(root.left == null && root.right == null && prev.left == root) {
////            sum += root.val;
////        }
////    }
//
////    //23.找树左下角的值(dfs)
////    private int maxDepth = 0;
////    private int res = 0;
////    public int findBottomLeftValue(TreeNode root) {
////        if(root.left == null && root.right == null) {
////            return root.val;
////        }
////        dfs(root, 0);
////        return res;
////    }
////
////    private void dfs(TreeNode root, int depth) {
////        if(root == null) {
////            return;
////        }
////        dfs(root.left, depth + 1);
////        dfs(root.right, depth + 1);
////        if(root.left == null && root.right == null && depth > maxDepth) {
////            res = root.val;
////            maxDepth = depth;
////        }
////    }
//
//    //24.找树左下角的值(queue)
//    public int findBottomLeftValue(TreeNode root) {
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        int res = 0;
//        while(!queue.isEmpty()) {
//            int size = queue.size();
//            boolean flag = true;
//            while(size > 0) {
//                TreeNode node = queue.poll();
//                if(flag) {
//                    res = node.val;
//                    flag = false;
//                }
//                if(node.left != null) {
//                    queue.offer(node.left);
//                }
//                if(node.right != null) {
//                    queue.offer(node.right);
//                }
//                size--;
//            }
//            flag = true;
//        }
//        return res;
//    }
//
////    //25.路径总和
////    private boolean dfs(TreeNode root, int target, int sum) {
////        if(root == null) {
////            return false;
////        }
////        sum += root.val;
////        if(root.left == null && root.right == null && sum == target) {
////            return true;
////        }
////        boolean left = dfs(root.left, target, sum);
////        boolean right = dfs(root.right, target, sum);
////        sum -= root.val;
////        return left || right;
////    }
////
////    public boolean hasPathSum(TreeNode root, int targetSum) {
////        if(root == null) {
////            return false;
////        }
////        return dfs(root, targetSum, 0);
////    }
//
//    //26.路径总和(优化，我又变强了？)
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        if(root == null) {
//            return false;
//        }
//        targetSum -= root.val;
//        if(root.left == null && root.right == null && targetSum == 0) {
//            return true;
//        }
//        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
//    }
//
//    //27.从中序与后序遍历序列构造二叉树
//    private TreeNode build(int[] inorder, int[] postorder, int left, int right) {
//        if(left > right) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[index--]);
//        //从中序遍历中找到节点值为 root.val 的下标
//        int midIndex = fundMidIndex(inorder, root.val);
//        root.right = build(inorder, postorder, midIndex + 1, right);
//        root.left = build(inorder, postorder, left, midIndex - 1);
//        return root;
//    }
//
//    private int fundMidIndex(int[] inorder, int val) {
//        for(int i = 0; i < inorder.length; i++) {
//            if(inorder[i] == val) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    private int index;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        index = postorder.length - 1;
//        return build(inorder, postorder, 0, postorder.length - 1);
//    }
//
//    //28.最大二叉树
//    private TreeNode creatBigTree(int[] nums, int left, int right) {
//        if(left > right) {
//            return null;
//        }
//        int maxValueIndex = fundIndex(nums, left, right);
//        TreeNode root = new TreeNode(nums[maxValueIndex]);
//        root.left = creatBigTree(nums, left, maxValueIndex - 1);
//        root.right = creatBigTree(nums, maxValueIndex + 1, right);
//        return root;
//    }
//
//    private int fundIndex(int[] nums, int left, int right) {
//        int index = left;
//        for(int i = left; i <= right; i++) {
//            if(nums[index] < nums[i]) {
//                index = i;
//            }
//        }
//        return index;
//    }
//
//    public TreeNode constructMaximumBinaryTree(int[] nums) {
//        return creatBigTree(nums, 0, nums.length - 1);
//    }
//
//    //29.合并二叉树
//    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//        if(root1 == null && root2 == null) {
//            return null;
//        }
//        if(root1 == null) {
//            return root2;
//        }
//        if(root2 == null) {
//            return root1;
//        }
//        root1.val += root2.val;
//        root1.left = mergeTrees(root1.left, root2.left);
//        root1.right = mergeTrees(root1.right, root2.right);
//        return root1;
//    }
//
//    //30.二叉搜索树中的搜索
//    public TreeNode searchBST(TreeNode root, int val) {
//        if(root == null) {
//            return null;
//        }
//        TreeNode left = searchBST(root.left, val);
//        if(root.val == val) {
//            return root;
//        }
//        TreeNode right = searchBST(root.right, val);
//        return left == null ? right : left;
//    }
//
//    //31.二叉搜索树的最小绝对差
//    private int dfs(TreeNode root) {
//        if(root == null) {
//            return Integer.MAX_VALUE;
//        }
//        int left = dfs(root.left);
//        if(prev != null) {
//            int tmp = Math.abs(root.val - prev.val);
//            left = left > tmp ? tmp : left;
//        }
//        prev = root;
//        int right = dfs(root.right);
//        return left > right ? right : left;
//    }
//
//    private TreeNode prev = null;
//    public int getMinimumDifference(TreeNode root) {
//        return dfs(root);
//    }
//
//
//
//    //32.二叉搜索树中的众数
//    public void dfs(TreeNode root, List<Integer> list) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.left, list);
//        if(list.isEmpty()) {
//            cur = root.val;
//            list.add(root.val);
//            count++;
//        } else {
//            if(cur == root.val) {
//                count++;
//            } else {
//                count = 1;
//                cur = root.val;
//            }
//        }
//        if(maxCount == count) {
//            list.add(root.val);
//        } else if(maxCount < count) {
//            list.clear();
//            list.add(root.val);
//            maxCount = count;
//        }
//        dfs(root.right, list);
//    }
//
//    private int maxCount = 0;
//    private int count = 0;
//    private int cur = 0;
//    public int[] findMode(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        dfs(root, list);
//        int[] res = new int[list.size()];
//        for(int i = 0; i < list.size(); i++) {
//            res[i] = list.get(i);
//        }
//        return res;
//    }
//}
//
//class Main {
//    public static void main(String[] args) {
////        int[] arr = {1,1,1,2,2,3};
////        [236,104,701,null,227,null,911]
//        TreeNode root1 = new TreeNode(1);
//        TreeNode root2 = new TreeNode(2);
//        TreeNode root3 = new TreeNode(2);
//
//        root1.right = root2;
//        root2.left = root3;
//        Solution1 solution1 = new Solution1();
//        solution1.findMode(root1);
//    }
//}